package main

import (
	"fmt"
)

/*
给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。

请你统计并返回 grid 中 负数 的数目。
思路：
1.二分搜索再次派上用场
2.有个特点是矩阵无论是按行还是按列都是递减，
二分查找grid[i][j]<0的点 返回
countNegatives[i:][0:j]+(m-i)*(n-j)再递归
注意边界的处理就行
*/
func countNegativesRe(grid [][]int, sx, sy, ex, ey int) int {
	//result := 0
	if sx > ex || ey > ey {
		return 0
	}
	for i := sx; i <= ex; i++ {
		my := BinarySearchDecreaseSmall(sy, ey, grid[i], -1)
		if my != -1 {
			result := (ey - my + 1) * (ex - i + 1)
			return countNegativesRe(grid, i+1, 0, ex, my-1) + result
		}
	}
	return 0
}

func countNegatives(grid [][]int) int {
	m := len(grid)
	if m == 0 {
		return 0
	}
	n := len(grid[0])
	return countNegativesRe(grid, 0, 0, m, n)

}

func BinarySearchDecreseEqualClosest(s, e int, arr []int, k int) int {
	if s > e {
		return -1
	}
	if s == e {
		if arr[s] == k {
			return s
		}
	}
	if s+1 == e {
		if arr[s] == k {
			return s
		}
		if arr[e] == k {
			return e
		}
		return -1
	}
	c := s + (e-s)/2
	if arr[c] > k {
		return BinarySearchDecreseEqualClosest(c+1, e, arr, k)
	}
	if arr[c] == k {
		result := BinarySearchDecreseEqualClosest(s, c-1, arr, k)
		if result != -1 {
			return result
		}
		return c
	}
	return BinarySearchDecreseEqualClosest(s, c-1, arr, k)
}

/*
前提是arr是单调递增的
在sorted arr数组中下标范围[s,e)中查找距离k最近的小于k的数的下标
没有就返回-1
*/
func BinarySearchDecreaseSmall(s, e int, arr []int, k int) int {
	if s > e || len(arr) < 1 {
		return -1
	}
	if s == e {
		if arr[s] <= k {
			return s
		}
		return -1
	}
	if s+1 == e {
		if arr[s] <= k {
			return s
		}
		if arr[e] <= k {
			return e
		}
		return -1
	}
	c := (e-s)/2 + s
	if arr[c] > k {
		return BinarySearchDecreaseSmall(c+1, e, arr, k)
	}
	//有可能c的前面还有==k的需要再处理下
	if arr[c] == k {
		cOther := BinarySearchDecreseEqualClosest(s, c-1, arr, k)
		if cOther != -1 {
			return cOther
		}
		return c
	}
	return BinarySearchDecreaseSmall(s, c, arr, k)
}

func main() {
	data := [][]int{{4, 3, 2, -1}, {3, 2, 1, -1}, {1, -1, -1, -2}, {2, -1, -1, -2}}
	r := countNegativesRe(data, 0, 0, 3, 3)
	fmt.Println(r)
	b := BinarySearchDecreaseSmall(0, 3, data[2], -1)
	fmt.Println(b)
}
